package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

public class Solution2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;

        //设置虚拟头节点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        /*carry表示进位*/
        int carry = 0;

        /*
        * 链表不为空时，不能停止
        * 还有进位时，不能停止
        * 链表不空不停止比较好理解。有进位不停止是什么原因？
        * 比如说99+9 = 108，会多出一个百位数字出来
        * */
        while(p1!=null || p2!=null || carry==1){
            //val记录本位加出来的值
            //先把上一位计算出来的进位值赋值给val，可0可1
            int val = carry;

            if (p1!=null){
                val += p1.val;
                p1 = p1.next;
            }
            if (p2!=null){
                val +=p2.val;
                p2 = p2.next;
            }

            /*计算当前进位，给下一位用*/
            carry = val/10;
            val = val % 10;

            ListNode newNode = new ListNode(val);
            p.next=newNode;
            p=p.next;
        }

        return dummy.next;
    }
}
